package twentytwenty;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Zahi
 * @Description:
 * @Date Created in 2020-12-14 11:12
 * @Modified By:
 */
public class ReadBinaryWatch_401 {
    public static void main(String [] args){
        int num = 1;
        System.out.println(readBinaryWatch(num));
    }
    // 下标索引在0-3范围内的表示的是小时,不在这个范围内的表示的是分钟;
    static Integer[] watch = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};

    static List<String> res = new ArrayList<>();
    public static List<String> readBinaryWatch(int num){
        dfs(2,0,0,0,0);
        return res;
    }

    private static void dfs(int num, int idx, int count, int hour, int minute) {

        // 剪枝;
        if (hour > 11 || minute > 59) {
            // 这些结果是要丢弃的;
            return;
        }

        // 凑足了数字,则需要添加结果;
        if (count == num) {
            StringBuffer sb = new StringBuffer();
            // 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
            sb.append(hour).append(":");
            // 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
            if (minute < 10) {
                sb.append("0").append(minute);
            } else {
                sb.append(minute);
            }
            res.add(sb.toString());
            return;
        }

        // 如果不用for循环,则需要自己添加递归终止判定;
        if (idx >= watch.length) {
            return;
        }


        // 不选;不选数字则count不需要加1;
        dfs(num, idx + 1, count, hour, minute);

        // 选;

        if (idx <= 3) { // 加到小时上;
            hour += watch[idx];
        } else {
            minute += watch[idx];
        }

        dfs(num, idx + 1, count + 1, hour, minute);

        if (idx <= 3) {
            hour -= watch[idx];
        } else {
            minute -= watch[idx];
        }
    }
}
